package org.example.myleet.p406;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 9 ms
 * 来自"镐锝铼氪"的妙解
 * 先对输入数组排序，h升序，k降序 从头循环遍历 当前这个人就是剩下未安排的人中最矮的人，他的k值就代表他在剩余空位的索引值 如果有多个人高度相同，要按照k值从大到小领取索引值
 */
public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    //按照身高排序
                    return o1[0] - o2[0];
                }
                //按照k降序
                return o2[1] - o1[1];
            }
        });
        //制造全部剩余空位的索引值[1,2,3.....,n]，n=人数
        List<Integer> indexes = new ArrayList<>(people.length);
        for (int i=0; i<people.length; i++) {
            indexes.add(i);
        }
        //下面是最妙的地方，这样理解，第二位的k数值是当前索引剩余空位中的位置，已经占领的空位从剩余空位中移除
        //可以这么做的原因是，按照身高升序，那么越小的身高的k代表的肯定是算上前面越多的人，而占据位置之后，后面更大的数在计算k的时候将忽略掉这个小的数，所以k代表前面忽略掉小的数之后的索引位置
        //例如有4、5、6、7四种身高，4的k代表的是前面4、5、6、7的个数，5的k代表的是前面5、6、7的个数，6的k代表的是前面6、7的个数，如此类推
        //因此要先找从身高小的开始按照k位置找到索引位置，安放好结果，并移除该索引位置，下一个身高查找索引位置的时候就可以忽略掉那个位置了
        //[ 0, 1, 2, 3, >4, 5 ] [ 4, 4 ] 4
        //[ 0, 1, >2, 3, 5 ]    [ 5, 2 ] 2
        //[ >0, 1, 3, 5 ]       [ 5, 0 ] 0
        //[ 1, >3, 5 ]          [ 6, 1 ] 3
        //[ 1, >5 ]             [ 7, 1 ] 5
        //[ >1 ]                [ 7, 0 ] 1
        //[ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]
        int[][] result = new int[people.length][2];
        for (int[] person : people) {
            Integer idx = indexes.remove(person[1]);
            result[idx][0] = person[0];
            result[idx][1] = person[1];
        }
        return result;
    }
}
